1. Field of the Invention
The invention relates to a polynomial divider which can perform, and apparatus including the polynomial divider which employ, Euclid's Algorithm to produce an error locator polynomial for use in performing error correction. In particular, the invention relates to a polynomial divider which can perform Euclid's Algorithm by iteratively solving both equations thereof to produce an error locator polynomial from an error syndrome polynomial; an error locator polynomial determining apparatus which includes the polynomial divider and a control unit for controlling the polynomial divider; and an error correction apparatus which includes the error locator polynomial determining apparatus.
2. Description of Related Art
Digital information signals made up of information data bytes are often encoded and transmitted through transmission mediums, such as, for example, optical record carriers. Such signals can represent audio, video and/or textual information. For example, those signals can be digital audio signals representing music or digital video signals representing pictures, full motion video or television signals.
When a digital information signal is encoded for transmission through a transmission medium, one or more error detection data bytes and error correction data bytes are typically added to the information data bytes of that digital information signal in a process which produces a coded digital signal (hereinafter referred to as a "coded signal"). A coded signal includes data bytes which include the information data bytes of a digital information signal and the one or more error detection data bytes and error correction data bytes added thereto.
To obtain a replica of a digital information signal from a coded signal (received from a transmission medium), a decoding process including error detection and, if necessary, error correction is used. Error correction becomes necessary when error detection reveals that one or more errors exist in one or more of the data bytes of an encoded signal. Error correction and error detection are processes which are performed in the binary field, i.e., GF(2).
Before erroneous data bytes of an encoded signal can be corrected, an error correction apparatus must first determine (a) where within the encoded signal errors exists and (b) what those errors are. An error correction apparatus makes that determination in two pre-correction steps.
In the first pre-correction step, the error correction apparatus uses an error syndrome polynomial produced by an error detection apparatus for the encoded signal to produce an error locator polynomial for that encoded signal. That step can be performed through means of a number of well known algorithms, including Euclid's Algorithm and Berlekamp's Algorithm. See Clark and Cain, Error-Correction Encoding for Digital Communications, chapter 5.4, pgs. 195-208, 1988 (3rd printing, Plenum Press).
Euclid's Algorithm is used to produce an error locator polynomial from an error syndrome polynomial by iteratively solving two equations: EQU Q.sub.i =MA.sub.i-2 /MA.sub.i-1 (quotient only), and (EQ. 1) EQU MA.sub.i =MA.sub.i-2 +Q.sub.i MA.sub.i-1, (EQ. 2)
for i incremented from 2 to n by 1, where n is the lowest value of i for which the degree of polynomial Q.sub.i is less than T, and T is a constant which specifies the maximum number of errors which can be error corrected. As one skilled in the art is aware, the value of T is dictated by the number of error detection and/or error correction data bytes included in a coded signal. Polynomial MA.sub.0 is equal to X.sup.2T (a polynomial constant), and polynomial MA.sub.1 is the error syndrome polynomial. Polynomial Q.sub.n is the error locator polynomial.
In the second pre-correction step, the error correction apparatus uses the error locator polynomial to obtain specific information about (a) the location where within the encoded signal one or more errors exist and (b) what those one or more errors are (all of that information is hereinafter referred to as "i & e information"). That step can be performed, for example, by means of the well known Chien search method. See Clark and Cain, chapter 5.3, pgs. 193-194. Once the i & e information has been obtained, erroneous data bytes of the encoded signal can be error corrected.
The equipment which is currently available to produce an error locator polynomial from an error syndrome polynomial is inefficient. That equipment is too slow for current needs, and/or it requires more hardware than is necessary.